Programs executing on data processing systems often rely on peripheral devices to send, receive, or manipulate data. A program may view the peripheral's operations as atomic units (i.e. indivisible, starting at a first time and finishing some time later) but the peripheral may actually have to perform many sub-tasks to complete the work requested of it. For example, a network interface instructed to send a data packet may be required to execute a number of memory transactions to obtain all the data for the packet from memory.
In a computer system where several threads of execution are proceeding concurrently (either truly simultaneously on multiple processors or logically simultaneously by time-slicing), a constant stream of memory transactions may be generated, executed and retired by various subsystems. In general, the subsystems cannot know how the transactions are related, and therefore the system must execute transactions in the same order they were generated to avoid causing incorrect program operation.
The basic programming semantic supported by this strict ordering requirement is called the producer/consumer (“P/C”) relationship. P/C relationships can appear in many complex forms, but a simple example shows how ordering changes can cause errors. Imagine two programs executing on a system. The first program produces data and the second operates on (“consumes”) the data. In a canonical P/C relationship, the first program produces a quantity of data, then sets a flag to indicate to the second program that there is data for it to process. The second program monitors the flag, and when it is set, begins to consume the data. However, both “data” and “flag” may simply be values in computer memory shared between the processes—and indistinguishable to a peripheral that sets them. If the first program generates a sequence of memory transactions that result in data being placed in memory, then generates a final memory transaction to set the flag, but the system re-orders the transactions so that the flag is set before all the data is ready in memory, then the second program may begin working prematurely and consume data that has not yet been produced. Thus, re-ordering memory transactions can break P/C relationships.
Nevertheless, the ability to re-order memory transactions can provide tremendous flexibility to a computer system. For example, if a first transaction involves a resource (such as a cache location) that is temporarily unavailable, a system that can execute a second transaction that was generated after the first transaction can make forward progress, rather than stalling all execution until the resource becomes available to complete the first transaction. Identifying and exploiting circumstances in which re-ordering transactions is safe can produce overall system performance gains.